class Solution {
    #define maxn 100010
    #define ull unsigned long long
    #define B 271
    ull power[maxn];
    ull hash[maxn];
public:
    void init(string s)
    {
        power[0]=1;
        hash[0]=s[0];
        for(int i=1;i<s.size();i++)
        {
            hash[i]=hash[i-1]*B+s[i];
            power[i]=power[i-1]*B;
        }
    }
    ull get(int l,int r)
    {
        if(l==0)
            return hash[r];
        return hash[r]-hash[l-1]*power[r-l+1];
    }
    string longestPrefix(string s) {
        if(s.size()==0)
            return "";
        init(s);
        for(int i=s.size()-1;i>=1;i--)
        {
            if(get(0,i-1) == get(s.size()-i,s.size()-1))
            {
                return s.substr(0,i);
            }
        }
        return "";
    }
};